package main

//整数数组 nums 按升序排列，数组中的值 互不相同 。
//
// 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[
//k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2
//,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
//
// 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
//
//
//
// 示例 1：
//
//
//输入：nums = [4,5,6,7,0,1,2], target = 0
//输出：4
//
//
// 示例 2：
//
//
//输入：nums = [4,5,6,7,0,1,2], target = 3
//输出：-1
//
// 示例 3：
//
//
//输入：nums = [1], target = 0
//输出：-1
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 5000
// -10^4 <= nums[i] <= 10^4
// nums 中的每个值都 独一无二
// 题目数据保证 nums 在预先未知的某个下标上进行了旋转
// -10^4 <= target <= 10^4
//
//
//
//
// 进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
// Related Topics 数组 二分查找 👍 1878 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
func search(nums []int, target int) int {
	// 如果nums就是一个升序数组，那就直接使用二分查找即可
	// 如果不是升序数组，就从中间拆开，至少有一半是升序的
	// 如果是升序的，看一下target在不在左右边界，在的话继续使用二分查找
	// 如果target不在升序数组的左右边界里，那就继续看另一半数组是不是升序数组
	return mySearch(nums, 0, len(nums)-1, target)
}

func mySearch(nums []int, left, right, target int) int {
	if nums[left] <= nums[right] {
		return binarySearch(nums, left, right, target)
	}
	if left+1 == right {
		if nums[left] == target {
			return left
		}
		if nums[right] == target {
			return right
		}
		return -1
	}
	mid := (left + right) / 2
	a := mySearch(nums, left, mid, target)
	if a != -1 {
		return a
	}
	b := mySearch(nums, mid, right, target)
	if b != -1 {
		return b
	}
	return -1
}

func binarySearch(nums []int, left, right, target int) int {
	if target < nums[left] || target > nums[right] {
		return -1
	}
	for left <= right {
		mid := (left + right) / 2
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

//leetcode submit region end(Prohibit modification and deletion)
